#include <bits/stdc++.h>

using namespace std;

#define N 2000
int n, C, dp[N];
int w[N], v[N], m[N];
int new_n;
int new_w[N], new_c[N], new_m[N];

int main()
{
    int n;
    cin >> n >> C;
    for(int i = 1; i <= n; i++)
    {
        cin>>w[i]>>v[i];
        m[i] = C / w[i] + 1;
    }

    int new_n = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m[i]; j<<=1)
        {
            m[i] -= j;
            new_c[++new_n] = j*w[i];
            new_w[new_n] = j*v[i];
        }
        if(m[i])
        {
            new_c[++new_n] = m[i] * w[i];
            new_w[new_n] = m[i] * v[i];

        }
    }

    for(int i = 1; i <= new_n; i++)
    {
        for(int j = C; j >= new_c[i]; j--)
        {
            dp[j] = max(dp[j],dp[j - new_c[i]] + new_w[i]);

        }
    }
    cout << dp[C] << endl;
    return 0;
}